#!/bin/python
import sys, os, random, heapq, operator, copy, collections

n = 0
m = 0
in_file_name = None
out_file_name = None
problem = None

class Operation:
    def __init__(self, job, machine, time, duration, prevop, seq):
        self.job = job
        self.machine = machine
        self.time = time
        self.duration = duration
        self.prevop = prevop
        self.seq = seq

    def est(self):
        if self.prevop is not None and self.prevop.time is not None:
            return self.prevop.time + self.prevop.duration
        else:
            return 0

    def ft(self):
        return self.time + self.duration

    def __str__(self):
        return "(j%s m%s t%s d%s)" % (self.job, self.machine, self.time, self.duration)

    def __repr__(self):
        return self.__str__()
    #
    # def __cmp__(self, other):
    #     return (self.time + self.duration) - (other.time + other.duration)


def create_problem(in_file):
    """ Create a reusable representation structure for the problem """
    global n, m
    problem_description = in_file.readline()
    n, m = in_file.readline().split()
    n = int(n)
    m = int(m)
    problem = []
    for job_id, line in enumerate(in_file):
        line_iter = iter(line.split())
        prevop = None
        seq = 0
        for routing in range(m):
            machine_id = int(line_iter.next())
            duration = int(line_iter.next())
            op = Operation(job_id, machine_id, 0, duration, prevop, seq)
            problem.append(op)
            prevop = op
            seq += 1
    return problem, n, m

def random_candidate(problem):
    """ Create a random solution """
    problem, n, m = problem
    iterators = []
    for i in range(n):
        sequence = []
        for j in range(m):
            sequence.append(problem[i*m+j])
        iterators.append(iter(sequence))
    candidate = [[] for m1 in range(m)]
    eft = [0 for i in range(m)]
    while len(iterators) > 0:
        idx = random.randint(0, len(iterators)-1)
        it = iterators[idx]
        try:
            op = it.next()
            op.time = max(eft[op.machine], op.est())
            eft[op.machine] = op.time + op.duration
            candidate[op.machine].append(op)
        except StopIteration:
            iterators.remove(it)
            continue
    return candidate

def swap(c, x, y):
    """ Swap 2 operation on the same resource """
    resource = c[x]
    resource[y], resource[y+1] = resource[y+1], resource[y]

def neighbor_candidates(c):
    """ Return all candidates """
    neighbors = []
    for x, resource in enumerate(c):
        for y in range(len(resource)-1):
            swap(c, x, y)
            compact(c)
            cmax = objective(c)
            swap(c, x, y)
            heapq.heappush(neighbors, (cmax, (x, y)))
    return neighbors

def eft(op):
    """ Earliest finish time of an operation """
    return op.time + op.duration

def makespan2(candidate):
    """ Cmax or makespan """
    return max(map(eft, map(operator.itemgetter(-1), candidate)))

def makespan(candidate):
    """ Cmax or makespan """
    return max(map(eft, map(operator.itemgetter(-1), candidate)))

def twft(candidate):
    """ Total weighted flow time """
    return sum(map(eft, map(operator.itemgetter(-1), candidate)))

def compact(candidate):
    """ Compact candidate after the swap """
    qs = []
    for resource in candidate:
        q = []
        for op in resource:
            op.time = None
            heapq.heappush(q, (op.seq, op))
        qs.append(q)
    eft = [0 for i in range(m)]
    while len(qs) > 0:
        idx = random.randint(0, len(qs) - 1)
        q = qs[idx]
        if len(q) == 0:
            qs.remove(q)
            continue
        seq, op = heapq.heappop(q)
        if op.prevop is not None and op.prevop.time is None:
            heapq.heappush(q, (seq, op))
            continue
        op.time = max(eft[op.machine], op.est())
        eft[op.machine] = op.time + op.duration

    for resource in candidate:
        resource.sort(key=lambda op: op.ft())

def simulated_annealing(candidate):
    """
    Simulated Annealing is based on the descriptions in Hoos' SLS
    and Russel & Norvig's AIMA, but has not been fully developed
    therefore probability of acceptance does not depend on
    the delta of hill climbing (no time).
    """
    best = copy.deepcopy(candidate)
    best_min = objective(best)
    current = candidate
    t = (n+m)
    while True:
        t *= 0.95
        if t < 0.1:
            return best
        neighbors = neighbor_candidates(current)
        successor_min, (x, y) = heapq.heappop(neighbors)
        if successor_min < best_min:
            swap(current, x, y)
            compact(current)
            best = copy.deepcopy(current)
            best_min = objective(best)
            #print '+',
        elif random.random() < t:
            heapq.heappush(neighbors, (successor_min, (x, y)))
            idx = random.randint(0, len(neighbors) - 1)
            successor_min, (x, y) = neighbors[idx]
            swap(current, x, y)
            compact(current)
            o = objective(current)
            if o < best_min:
                best = copy.deepcopy(current)
                best_min = objective(best)
            #print '~',
        else:
            pass#print '/',

def save(best):
    out_file = open(out_file_name, 'w')
    out_file.write(str(makespan(best)) + ' ' + str(twft(best)) + '\n')
    for resource in best:
        for op in resource:
            out_file.write(str(op.job) + ' ' + str(op.time) + ' ')
        out_file.write('\n')
    out_file.close()

if __name__ == '__main__':
    if len(sys.argv) == 4:
        program_name, in_file_name, out_file_name, obj_function = sys.argv
    else:
        print 'Program requires 3 arguments: <input_file>, <output_file>, <objective function{0,1}>'
        os._exit(0)
    if obj_function == '0':
        objective = makespan
    elif obj_function == '1':
        objective = twft
    else:
        objective = makespan
    in_file = open(in_file_name)
    problem = create_problem(in_file)
    in_file.close()

    best = random_candidate(problem)
    best_min = objective(best)
    for i in range(m+n):
        candidate = simulated_annealing(random_candidate(problem))
        candidate_min = objective(candidate)
        if candidate_min < best_min:
            best_min = candidate_min
            best = copy.deepcopy(candidate)
        save(best)

